
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
https://www.lintcode.com/problem/cutting-a-rod/description
"""

class Solution:
    """
    @param prices: the prices
    @param n: the length of rod
    @return: the max value
    """
    def cutting(self, prices, n):
        # return self.cutting_method1(prices, n)
        # return self.cutting_method2(prices, n)
        return self.cutting_method3(prices, n)

    def cutting_method2(self, prices, n):
        self.max_price = [0] * (n+1)
        self.tmp_max = [0] * (n+1)

        for price_idx in range(len(prices)):
            cur_len = price_idx + 1
            cnt = n // cur_len

            for cnt in range(0, cnt+1):
                aug_len = cnt * cur_len
                aug_price = cnt * prices[price_idx]

                for max_len in range(n+1):
                    if aug_len + max_len > n:
                        break

                    new_len = aug_len + max_len
                    self.tmp_max[new_len] = max(self.tmp_max[new_len], self.max_price[new_len], aug_price + self.max_price[max_len])
                    # print(
                    #     # "price_idx, cnt, aug_len, max_len_idx: "
                    #     "price_idx ", price_idx,
                    #     "cnt ", cnt,
                    #     "aug_len ", aug_len,
                    #     "aug_price ", aug_price,
                    #     "max_len ", max_len,
                    #     "new_len ", new_len,
                    #     "tmp_max ", self.tmp_max[new_len],
                    #     self.tmp_max
                    # )

                # print()

            # print("end price_idx all cnt, change ===================  =====================", price_idx, cnt)
            # if cnt > 0:
            #     for idx in range(n+1):
            #         self.max_price[idx] = max(self.max_price[idx], self.tmp_max[idx])
            self.max_price = self.tmp_max
            self.tmp_max = [0] * (n+1)

        return self.max_price[-1]

    def cutting_method3_bug_fix_me(self, prices, n):
        self.max_price = [0] * (n+1)

        for price_idx in range(len(prices)):
            cur_len = price_idx + 1
            cnt = n // cur_len
            aug_len = cur_len
            aug_price = prices[price_idx]

            for cnt in range(1, cnt+1):
                for max_len in range(n+1):
                    if aug_len + max_len > n:
                        break
                    new_len = aug_len + max_len
                    self.max_price[new_len] = max(self.max_price[new_len], aug_price + self.max_price[max_len])

        return self.max_price[-1]

    def cutting_method3(self, prices, n):
        self.max_price = [0] * (n+1)

        for price_idx in range(len(prices)):
            cur_len = price_idx + 1
            cnt = n // cur_len
            aug_len = cur_len
            aug_price = prices[price_idx]

            # for cnt in range(1, cnt+1):
            for max_len in range(n+1):
                if aug_len + max_len > n:
                    break
                new_len = aug_len + max_len
                self.max_price[new_len] = max(self.max_price[new_len], aug_price + self.max_price[max_len])

        return self.max_price[-1]

    def cutting_method1(self, prices, n):
        self.memory = {}
        self.prices = prices
        self.n_item = len(self.prices)

        return self.max_cut_rec_from_min(n, min_price_idx=0)

    def max_cut_rec_from_min(self, remain_len, min_price_idx):
        min_price_len = min_price_idx + 1
        if remain_len < min_price_len:
            return 0

        if remain_len == min_price_len:
            return self.prices[min_price_idx]

        key = (remain_len, min_price_idx)
        max_price = self.memory.get(key)

        if max_price is not None:
            # print("hit ", remain_len, min_price_idx)
            return max_price

        max_price = 0
        for min_idx in range(min_price_idx, self.n_item):
            min_len = min_idx + 1
            min_price = self.prices[min_idx]
            if remain_len < min_len:
                break

            max_price = max(max_price, min_price + self.max_cut_rec_from_min(remain_len-min_len, min_idx))

        self.memory[key] = max_price
        return max_price


def test():
    s = Solution()

    prices1 = [1, 5, 8, 9, 10, 17, 17, 20]
    prices2 = [3, 5, 8, 9, 10, 17, 17, 20]
    prices3 = [12,22,23,28,28,38,41,46,56,59,63,67,70,70,79,89,95,103,113,116,121,123,126,126,130,132,132,142,151,151,158,159,164,173,177,178,179,182,191,195,200,206,211,219,229,235,243,252,256,259,260,265,272,282,289,292,302,307,310,310,316,322,325,333,340,344,346,353,353,353,356,360,367,374,382,384,392,396,399,399,403,406,412,422,425,428,433,435,438,446,455,463,464,464,470,477,478,488,496,505,510,511,511,515,525,527,534,535,536,538,538,542,544,550,554,559,569,569,572,578,585,594,600,607,616,621,621,624,624,630,634,635,637,638,639,645,650,656,659,662,668,668,671,674,684,688,695,702,703,703,707,715,722,728,736,736,738,742,751,760,764,771,779,783,791,801,811,821,823,827,834,836,846,856,866,871,874,879,885,895,897,903,903,903,911,915,920,924,934,940,944,954,958,960,963,964,971,979,984,987,991,997,1006,1011,1016,1021,1027,1031,1038,1045,1053,1053,1057,1057,1057,1067,1069,1074,1076,1086,1087,1091,1092,1101,1101,1107,1110,1116,1117,1124,1127,1134,1139,1142,1149,1152,1153,1162,1164,1164,1169,1173,1180,1190,1196,1203,1205,1212,1219,1228,1228,1228,1230,1235,1238,1246,1254,1264,1270,1273,1283,1292,1295,1301,1308,1311,1315,1318,1321,1326,1335,1337,1345,1351,1360,1360,1362,1370,1371,1378,1383,1383,1392,1402,1405,1415,1424,1424,1426,1432,1438,1445,1453,1458,1460,1463,1469,1478,1483,1489,1499,1506,1513,1519,1526,1531,1535,1540,1549,1553,1554,1562,1569,1578,1584,1584,1593,1596,1606,1606,1616,1619,1625,1627,1636,1641,1645,1649,1650,1653,1656,1664,1668,1670,1678,1686,1692,1699,1702,1707,1717,1722,1722,1726,1727,1735,1741,1741,1741,1745,1754,1755,1757,1767,1775,1778,1778,1784,1792,1798,1808,1808,1815,1815,1819,1819,1829,1830,1836,1837,1847,1851,1853,1861,1866,1872,1881,1888,1897,1905,1906,1916,1920,1920,1929,1931,1940,1945,1955,1960,1967,1976,1981,1987,1995,2003,2003,2013,2023,2031,2040,2040,2042,2049,2049,2055,2064,2074,2077,2085,2086,2090,2100,2100,2109,2114,2117,2124,2126,2128,2133,2134,2141,2142,2146,2152,2153,2160,2163,2164,2174,2180,2188,2193,2202,2203,2207,2217,2223,2224,2234,2235,2243,2245,2255,2264,2273,2273,2278,2286,2294,2295,2299,2300,2304,2311,2317,2321,2324,2328,2330,2339,2343,2348,2352,2355,2358,2360,2366,2371,2379,2380,2389,2392,2396,2400,2404,2412,2415,2425,2428,2432,2436,2441,2441,2450,2454,2459,2459,2461,2466,2471,2478,2488]


    # prices1 = [1, 5]
    # print( s.cutting(prices1, 2) )
    # print( s.cutting(prices1, 8) )
    # print( s.cutting(prices1, 8) )
    # print( s.cutting(prices2, 6) )
    # assert s.cutting(prices1, 8) == 22
    # assert s.cutting(prices2, 8) == 24

    res = s.cutting(prices3, 494)
    # print(res)
    assert res == 5928


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
